class Solution {
public:
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        // write your code here
        vector<int> res;
        vector<int>::iterator it1 = A.begin();
        vector<int>::iterator it2 = B.begin();

        while (it1 != A.end() && it2 != B.end()) {
            if (*it1 < *it2) {
                res.push_back(*it1);
                it1++;
            } else {
                res.push_back(*it2);
                it2++;
            }
        }

        while (it1 != A.end()) {
            res.push_back(*it1);
            it1++;
        }

        while (it2 != B.end()) {
            res.push_back(*it2);
            it2++;
        }

        return res;
    }
};

class Solution {
public:
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        // write your code here
        if (A.size() < B.size()) {
            vector<int> tmp = A;
            A = B;
            B = tmp;
        }

        for (int i = 0; i < B.size(); i++) {
            int target = B[i];
            int left = 0;
            int right = A.size() - 1;

            while (left + 1 < right) {
                int mid = (left + right) / 2;
                if (A[mid] <= target) {
                    left = mid;
                } else {
                    right = mid;
                }
            }

            vector<int>::iterator it = A.begin();
            if (target < A[left]) {
                it += left;
            } else if (target > A[right]) {
                it += right + 1;
            } else {
                it += right;
            }

            A.insert(it, target);
        }

        return A;
    }
};
